class Solution {
public:
    int candy(vector<int> &ratings) {
        int n=ratings.size();
        if (n==0) return 0;
        vector<int> degree(n,0);
        for (int i=0;i<n;i++) {
            if (i>=1 && ratings[i-1]<ratings[i]) ++degree[i];
            if (i+1<n && ratings[i+1]<ratings[i]) ++degree[i];
        }
        vector<int> now, last;
        for (int i=0;i<n;i++)
            if (degree[i]==0) now.push_back(i);
        int ans=0, weight=1;
        while (now.size()>0) {
            ans+=weight*now.size();
            ++weight;
            last.clear();
            last.swap(now);
            for (int i=0;i<last.size();i++) {
                if (last[i]+1<n && ratings[last[i]]<ratings[last[i]+1]) {
                    --degree[last[i]+1];
                    if (degree[last[i]+1]==0) now.push_back(last[i]+1);
                }
                if (last[i]-1>=0 && ratings[last[i]]<ratings[last[i]-1]) {
                    --degree[last[i]-1];
                    if (degree[last[i]-1]==0) now.push_back(last[i]-1);
                }
            }
        }
        return ans;
    }
};
